#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include "stack.h"


void PrintArry(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int x = *p1;
	*p1 = *p2;
	*p2 = x;
}

void InsertSort(int* a, int n)
{
	//多趟排序
	for (int i = 1; i < n; i++)
	{
		//单趟比较交换
		int end = i-1;
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > temp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;

	}
}

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[right] > a[mid])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

//hoare方法
//void QuickSort(int* a, int left, int right)
//{
//	//递归条件
//	if (left>=right)
//	{
//		return;
//	}
//
//	int begin = left;
//	int end = right;
//	////随机选keyi
//	//int randi = left + (rand() % (right - left));
//	//Swap(&a[left], &a[randi]);
//
//	//三数取中
//	int mid = GetMidNumi(a, left, right);
//	if(mid!=left)
//	Swap(&a[left], &a[mid]);
//
//	int keyi = left;
//	while (left < right)
//	{
//		//右边找小
//		while (left<right && a[right] >= a[keyi])
//		{
//			right--;
//		}
//		//左边找大
//		while (left < right && a[left] <= a[keyi])
//		{
//			left++;
//		}
//
//		Swap(&a[left], &a[right]);
//
//	}
//
//	Swap(&a[keyi], &a[left]);
//	keyi = left;
//
//	//递归左右子序列
//	QuickSort(a, begin, keyi - 1);
//	QuickSort(a, keyi + 1, end);
//
//}

//挖坑法
//void QuickSort(int* a, int left, int right)
//{
//	//递归条件
//	if (left >= right)
//	{
//		return;
//	}
//
//	int begin = left;
//	int end = right;
//	////随机选keyi
//	//int randi = left + (rand() % (right - left));
//	//Swap(&a[left], &a[randi]);
//
//	//三数取中
//	int mid = GetMidNumi(a, left, right);
//	if (mid != left)
//		Swap(&a[left], &a[mid]);
//
//	int temp = a[left];
//	int hole = left;
//	while (left < right)
//	{
//		//右边找小
//		while (left < right && a[right] >= temp)
//		{
//			right--;
//		}
//		a[hole] = a[right];
//		hole = right;
//		//左边找大
//		while (left < right && a[left] <= temp)
//		{
//			left++;
//		}
//
//		a[hole] = a[left];
//		hole = left;
//
//	}
//
//	a[hole] = temp;
//
//	//递归左右子序列
//	QuickSort(a, begin, hole - 1);
//	QuickSort(a, hole + 1, end);
//
//}

//前后指针法
//void QuickSort(int* a,int left,int right)
//{
//	//递归条件
//	if (left>=right)
//	{
//		return;
//	}
//
//	int begin = left;
//	int end = right;
//	////随机选keyi
//	//int randi = left + (rand() % (right - left));
//	//Swap(&a[left], &a[randi]);
//
//	//三数取中
//	int mid = GetMidNumi(a, left, right);
//	if (mid != left)
//		Swap(&a[left], &a[mid]);
//
//	int keyi = left;
//	int prev = left;
//	int cur = left+1;
//	while (cur <= right)
//	{
//		/*if (a[cur] < a[keyi])
//		{
//			prev++;
//			Swap(&a[prev], &a[cur]);
//			cur++;
//		}
//		else
//		{
//			cur++;
//		}*/
//
//		if (a[cur] < a[keyi] && (prev++) != cur)
//			Swap(&a[cur], &a[prev]);
//		cur++;
//	}
//	Swap(&a[prev], &a[keyi]);
//	
//	//小区间优化——小区间使用直接插入排序
//	if ((right - left + 1) < 10)
//	{
//		//递归左右子序列
//		QuickSort(a, begin, prev - 1);
//		QuickSort(a, prev + 1, end);
//	}
//	else
//	{
//		InsertSort(a + left, right - left + 1);
//	}
//}

//递归改非递归
void QuickSortNonR(int* a, int left, int right)
{
	ST QS;
	STInit(&QS);
	//先入右再入左 确保先取出来的是左
	STPush(&QS, right);
	STPush(&QS, left);

	while (!STEmpty(&QS))
	{
		//取出左区间
		int begin = STTop(&QS);
		STPop(&QS);
		//取出右区间
		int end = STTop(&QS);
		STPop(&QS);

		//三数取中
		int mid = GetMidNumi(a, begin, end);
		if (mid != begin)
			Swap(&a[begin], &a[mid]);

		int keyi = begin;
		int prev = begin;
		int cur = begin + 1;
		while (cur <= end)
		{
			if (a[cur] < a[keyi] && (prev++) != cur)
				Swap(&a[cur], &a[prev]);
			cur++;
		}
		Swap(&a[prev], &a[keyi]);
		keyi = prev;

		if (keyi + 1 < end)
		{
			STPush(&QS, end);
			STPush(&QS, keyi+1);
		}
		if (begin < keyi-1)
		{
			STPush(&QS, keyi-1);
			STPush(&QS, begin);
		}
	}

	STDestroy(&QS);

}

int main()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	PrintArry(a, sizeof(a) / sizeof(a[0]));

	QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0])-1);
	PrintArry(a, sizeof(a) / sizeof(a[0]));

	return 0;

}